package sort;

import java.util.Arrays;

//快速排序
public class QuickSort1 {
    public static void main(String[] args) {
        int ary[] = {1, 3, 9, 56, 87, 49, 35};
        System.out.println(Arrays.toString(ary));
        System.out.println();

        quickSort(ary, 0, ary.length - 1);
        System.out.println(Arrays.toString(ary));
        System.out.println();
    }

    public static void quickSort(int[] ary, int start, int end) {
        //表示枢纽元位置的元素值
        int pivot = ary[end];

        //表示“左侧区域”的最大下标（最右侧元素的下标）
        int x = start - 1;

        //遍历数组片段,实现分出左右两个区域
        for (int i = start; i < end; i++) {
            if (ary[i] <= pivot) {
                if (i - x > 1) { //判断当前元素的左侧是否已存在大于枢纽元的元素
                    //将下标i与下标x+1位置的数据换位
                    int temp = ary[x + 1];
                    ary[x + 1] = ary[i];
                    ary[i] = temp;
                    x++; //x自增
                } else {
                    x = i;
                }
            }
        }

        //将枢纽元放在左右两个区域的中间
        //交换枢纽元与第一个大于枢纽元的位置的位置
        if (pivot < ary[x + 1]) {
            ary[end] = ary[x + 1];
            ary[x + 1] = pivot;
        }

        //如果左侧区域仍有多个元素，则递归
        //x若比需要处理的数组片段的最左侧元素下标大，则表示左侧区域超过1个元素
        if (x > start) {
            quickSort(ary, start, x);
        }

        //如果左侧区域仍有多个元素，则递归
        //提示：x是左侧区域的最大下标，其右侧还有1个枢纽元，如果存在右侧区域，
        //则起始下标为x+2
        if (end - x - 1 > 1) {
            quickSort(ary, x + 2, end);
        }
    }
}
